package 题目集.单调栈or队列.单调队列;

import org.junit.Test;

/**
 * https://leetcode.cn/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/description/
 */
public class 绝对差不超过限制的最长连续子数组 {

    public int longestSubarray(int[] nums, int limit) {
        int n = nums.length;
        // 定义两个队列，分别用来存储窗口中的最大值和最小值的索引
        int[] maxQueue=new int[n];
        int maxHead=0,maxTail=0;
        int[] minQueue=new int[n];
        int minHead=0,minTail=0;
        int res=0;
        // 使用一个for循环遍历数组nums
        for (int i = 0, j = 0; j < n; j++) {
            // 更新maxQueue
            while(maxHead!=maxTail&&nums[j]>nums[maxQueue[maxTail-1]]){
                maxTail--;
            }
            maxQueue[maxTail]=j;
            maxTail=(maxTail+1)%n;
            // 更新minQueue
            while(minHead!=minTail&&nums[j]<nums[minQueue[minTail-1]]){
                minTail--;
            }
            minQueue[minTail]=j;
            minTail=(minTail+1)%n;
            // 如果窗口中的最大值和最小值的差大于限制limit，就将窗口的左边界向右移动
            while (nums[maxQueue[maxHead]]-nums[minQueue[minHead]]>limit){
                if (maxQueue[maxHead]==i){
                    maxHead=(maxHead+1)%n;
                }
                if (minQueue[minHead]==i){
                    minHead=(minHead+1)%n;
                }
                i++;
            }
            // 更新结果res为当前窗口的长度和res的较大值
            res=Math.max(res,j-i+1);    //左闭右闭额外+1
        }
        // 返回结果res，即绝对差不超过限制的最长连续子数组的长度
        return res;
    }
    @Test
    public void test(){
        System.out.println(longestSubarray(new int[]{10,1,2,4,7,2},5));
    }
}
